package com.tgy.leetcode;


import java.util.Arrays;

public class _338_比特位计数 {

    public static int[] countBits(int num) {

        int[] bits = new int[num + 1];
        int count;
        for (int i = 1; i <= num; i++) {

            count = 0;
            int n = i;
            while (n > 0) {

                n ^= (((~n) + 1) & n);
                count++;
            }
            bits[i] = count;
        }

        return bits;


    }

    public static int[] countBits02(int num) {

        int[] bits = new int[num + 1];
        for (int i = 1; i <= num; i++) {

            bits[i] = bits[i >> 1];

            if ((i & 1) != 0) {

                bits[i]++;
            }
        }

        return bits;
    }

    public static int[] countBits01(int num) {

        int[] bits = new int[num + 1];
        for (int i = 1; i <= num; i++) {

            bits[i] = bits[(i - 1) & i] + 1;
        }

        return bits;
    }

    public static void main(String[] args) {

        long start = System.currentTimeMillis();
        countBits01(100000000);
        long end = System.currentTimeMillis();

        System.out.println(end - start);
//        String string = Arrays.toString(countBits(100000000));
//        System.out.println(string);
    }
}
